package leedcode_path.treeNoDE;

import java.util.*;

public class 二叉树的锯齿层序遍历 {
    /*
    * 给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。*/
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res=new ArrayList<List<Integer>>();
        if (root==null) return  res;
        Queue<TreeNode> que =new LinkedList<TreeNode>();
        que.offer(root);
        boolean flag=true;
        while (!que.isEmpty()){
            List<Integer> lis=new ArrayList<Integer>();
            int len=que.size();

            while (len>0){
                TreeNode temNode=que.poll();
                lis.add(temNode.val);
                if (temNode.left!=null) que.offer(temNode.left);
                if (temNode.right!=null) que.offer(temNode.right);
                len--;
            }
            if (flag){
                res.add(lis);
                flag=!flag;
            }else {
                Collections.reverse(lis);
                res.add(lis);
                flag=!flag;
            }

        }
        return res;

    }
}
